package first.codeTop.byteDance;

/**
 * @ClassName Leetcode42
 * @description:
 * @author: 荣燊
 * @create: 2021-07-26 10:19
 **/
public class Leetcode42 {
    // 接雨水，hard
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap1(height));
    }

    // 方法1：动态编程，
    // 从0开始，找到数组中从下标 i 到最左端最高的条形块高度 left_max。
    // 从size开始，找到数组中从下标 j 到最右端最高的条形块高度right_max。
    public static int trap1(int[] height) {
        if (height.length == 0 || height.length == 1) {
            return 0;
        }
        int res = 0;
        int size = height.length;
        int[] left_max = new int[size];
        int[] right_max = new int[size];
        left_max[0] = height[0];
        // 记录数组第i个元素的 最左边的最大值（包括第i位）
        for (int i=1; i<size; i++) {
            left_max[i] = Math.max(height[i], left_max[i-1]);
//            System.out.print("第"+i+"位的最左边的最大值："+left_max[i]+"/ ");
        }
//        System.out.println();
        // 记录数组第i个元素的 最右边的最大值（包括第i位）
        right_max[size-1] = height[size-1];
        for (int i=size-2; i>=0; i--) {
            right_max[i] = Math.max(height[i], right_max[i+1]);
//            System.out.print("第"+i+"位的最右边的最大值："+right_max[i]+"/  ");
        }
        // 如何分析这两个数组，第0位和第size-1位是桶的边缘，所以不用统计该位的水位
        for (int i=1; i<size-1; i++) {
            res += Math.min(left_max[i], right_max[i]) - height[i];
        }
        return res;
    }

    // 方法2：双指针
    public static int trap2(int[] height) {
        return 0;
    }

}
